#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1944. 队列中可以看到的人数
// 【难度】困难
// 【提交】 https://leetcode.cn/problems/number-of-visible-people-in-a-queue/submissions/663983196/
// 【标签】栈、数组、单调栈、第57场双周赛
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> cansee(n, 0);   // cansee[i] 表示 i 能看到多少人
        stack<int> stk;             // 单调递减栈，存下标

        for (int i = 0; i < n; ++i) {
            // 1. 把栈里所有 <= 当前高度的都弹掉
            while (!stk.empty() && heights[stk.top()] <= heights[i]) {
                ++cansee[stk.top()]; // 栈顶这个人可以看到当前人
                stk.pop();
            }
            // 2. 如果栈不空，栈顶那个人也能看到当前人
            if (!stk.empty()) {
                ++cansee[stk.top()];
            }
            stk.push(i);
        }
        return cansee;
    }
};